rtk 2009

2009.1.1

Kolikokrat najmanjši

1. podnaloga

Naloga

Napiši funkcijo kolikokrat_najmanjši(dat), ki prebere zaporedje celih števil in izpiše, kolikokrat se v tem zaporedju pojavi najmanjše število.

Vhodni podatki

tekstovna datoteka zaporedje.txt z zaporedjem števil, vsakim v svoji vrstici. Prva vrstica je prazen niz

  10
  5
  8
  5
  5
  20
  7

Izhodni podatki

Število pojavitev najmanjšega števila v zaporedju.

Uradna rešitev

def kolikokrat_najmanjsi(datoteka):
    '''Prebere datoteko in vrne število pojavitev najmenjšega števila v zaporedju'''
    dat = open(datoteka, 'r', encoding='utf-8').readlines()
    zaporedje = []
    for vrstica in dat[1:]:
        zaporedje.append(int(vrstica.strip('\n')))
    najmanjsi = min(zaporedje)
    return sum(1 for clen in zaporedje if clen == najmanjsi)

2009.1.2

Označevanje kovancev

1. podnaloga

Izdelovalec spominskih kovancev bi rad izdelal serijo dvajsetih milijonov kovancev, vsak pa naj bi imel enolično oznako, sestavljeno iz števk in nekaterih velikih črk. Oznaka naj bi bila dovolj kratka, da si jo je lažje zapomniti ali prepisati, hkrati pa bi bilo pametno, da ne uporabimo v oznaki črk, ki so preveč podobne števkam ali drugim črkam, zato da se izognemo najbolj pogostim zmotam pri odčitavanju oznake. Tako izločimo črke I, L, O, Q, S, U, uporabimo pa vse ostale črke angleške abecede in vse števke od $0$ do $9$. Tako nam ostane $30$ znakov:

  0123456789ABCDEFGHJKMNPRTVWXYZ

Izkaže se, da oznaka, sestavljena iz $5$ znakov tega nabora, zadošča, da enolično označimo (oštevilčimo) vse kovance.

Naloga

Napiši funkcijo oznaci_kovance(znaki), ki izpiše oznake za prvih dvajset milijonov različnih kovancev, sestavljenih iz gornjih $30$ znakov, dolžine 5. Oznake naj bodo leksikografsko urejene.

Vhodni podatki

niz z znaki

  znaki = '0123456789ABCDEFGHJKMNPRTVWXYZ'

Izhodni podatki

Tabela T s prvimi $20$-imi miljoni oznak za kovance, vsaka šifra naj bo shranjena v svojem naboru. Primer za enomestne cifre:

   [('0',), ('1',), ('2',), ('3',), ('4',), ('5',), ('6',), ('7',), ('8',), ('9',),
   ('A',), ('B',), ('C',), ('D',), ('E',), ('F',), ('G',), ('H',), ('J',), ('K',),
   ('M',), ('N',), ('P',), ('R',), ('T',), ('V',), ('W',), ('X',), ('Y',), ('Z',)]

Uradna rešitev

from itertools import combinations_with_replacement
znaki = '0123456789ABCDEFGHJKMNPRTVWXYZ'
def oznaciKovance(znaki):
    return list(combinations_with_replacement(znaki,5))[:20000000]

2009.1.3

Citiranje

1. podnaloga

Recimo, da bi radi citirali razne strani iz neke knjige; to naredimo tako, da naštejemo številke teh strani v strogo naraščajočem vrstnem redu, na primer $2, 5, 6, 8, 11, 28, 29, 30, 31, 67$. Če se v tem seznamu kdaj pojavita dve ali več zaporednih strani, ga lahko zapišemo krajše: obdržimo le prvo in zadnjo številko strani iz take skupine več zaporednih številk, med njiju pa zapišimo vezaj: $2, 5–6, 8, 11, 28–31, 67$.

Naloga

Napiši funkcijo citiraj(sezStrani), ki prebere seznam številk strani, vrne pa nov seznam, kjer so zaporedne strani en element in pisane z vezajem.

Vhodni podatki

Seznam integerjev s številkami strani

  [ 2, 5, 6, 8, 11, 28, 29, 30, 31, 67]

V seznamu so številke strani že podane v naraščajočem vrstnem redu, vse pa so cela števila, večja od $0$. Predpostaviš lahko, da je v vhodnem seznamu vsaj ena številka in da se nobena številka v njem ne pojavi več kot enkrat.

Izhodni podatki

Seznam nizov s strnjenimi zaporednimi stranmi.

  ['2', '5–6', '8', '11', '28–31', '67'.]

Uradna rešitev

def citiraj(sez_strani):
    '''V seznamu skrči zaporedne številke strani npr. 1,2,3,4 v 1-4
       in vrne nov seznam'''
    skrcen_seznam = []
    sez_strani.append(0)  # dodamo, da ne bo problemov z indeksi
    i = 0
    while i < len(sez_strani) - 1:
        # preverimo naslednjo
        if sez_strani[i] == sez_strani[i + 1] - 1:
            Od = sez_strani[i]
            Do = sez_strani[i + 1]
            # preverimo, do kam gre zaporedje
            for j in range(i, len(sez_strani) - 1):
                if sez_strani[j + 1] == sez_strani[j + 2] - 1:
                    Do = sez_strani[j + 2]
                else:
                    break
            skrcen_seznam.append(str(Od) + '-' + str(Do))
            i += Do - Od + 1
        else:
            skrcen_seznam.append(str(sez_strani[i]))
            i += 1
    return skrcen_seznam

2009.1.4

1. podnaloga

Po tisočletjih življenja v komuni se nekega dne tudi v deželo Smrkcev prikrade kapitalizem. V času tranzicije so si postopno razgrabili svojo vasico tako, da si je osem tajkunosmrkcev eden za drugim prilastilo po polovico še nerazdeljenega ozemlja.

Vsak je lahko izbiral med severno, južno, zahodno in vzhodno polovico preostanka. Napiši podprogram Nerazdeljeno, ki ugotovi, katero območje je ostalo nerazdeljeno. Celotna vas Smrkcev se razprostira na kvadratni površini velikosti 256 × 256 metrov, koordinate vasi pa se merijo od severozahodnega oglišča (0, 0) do skrajnega jugovzhoda (256, 256).

Koordinate poljubnega pravokotnega območja znotraj vasi lahko zapišemo kot zaporedje štirih vrednosti (najprej x in y koordinata SZ oglišča in nato x in y koordinata JV oglišča); celotna vas ima torej koordinate (0, 0, 256, 256).

Naloga

Napiši funkcijo $nerazdeljeno(delitve)$, ki naj v seznamu vrne koordinate območja, ki ostane nerazdeljeno po vseh delitvah iz niza delitve.

Vhodni podatki

Parameter $delitve$ je niz osmih znakov (S, J, Z in V), ki opisujejo izbire tajkunosmrkcev v takem vrstnem redu, po kakršnem so si delili vas.

Izhodni podatki

Tvoj podprogram naj vrne seznam s koordinati območja [z, s, v, j], ki ostane nerazdeljeno po vseh delitvah iz niza $delitve$

Primer

Recimo, da dobimo niz

  'SSZJVVJS'

Prvi tajkunosmrkec si je tako vzel severno (zgornjo) polovico celotnega ozemlja, torej ostane južna (spodnja) polovica:

  [0, 128, 256, 256]

Drugi izbere severno polovico preostanka, ostane

  [0, 192, 256, 256]

Tretji izbere zahodno (levo) polovico, ostane

  [128, 192, 256, 256]

Nato vzame četrti južno polovico, ostane

  [128, 192, 256, 224]

Ostali štirje vzamejo vzhodno, vzhodno, južno in severno:

  [128, 192, 192, 224]
  [128, 192, 160, 224]
  [128, 192, 160, 208]
  [128, 200, 160, 208]

Zadnji izpis je torej naš končni odgovor

Komentar

Na tekmovanju so zahtevali izpis na standarni izhod. Dodaten del naloge na tekmovanju je opis sprememb v kodi ob spremembi velikosti ozemlja in števila tajkunsmrkcev.

Uradna rešitev

def nerazdeljeno(delitve):
    '''poračuna, katero območje v smkcolandiji(velikosti 256x256) je ostalo nerazdeljeno po
       izboru osmih tajkun smrkcov'''
    s,j,z,v = 0, 256, 0, 256
    for izborSmrkca in delitve:
        if izborSmrkca == 'S': s = (s + j) / 2
        elif izborSmrkca =='J': j = (s + j) / 2
        elif izborSmrkca == 'Z': z = (z + v) / 2
        elif izborSmrkca == 'V': v = (z + v) / 2
    return [z,s,v,j]

2009.2.1

Soglasniški podnizi

1. podnaloga

Na datoteki imamo zapisane besede, vsako v svoji vrstici. V njih nastopajo le male črke angleške abecede, nobene številke ali ločila ni. Nobena beseda ni daljša od 100 znakov. Zanima nas beseda, v kateri se nahaja najdaljši strnjeni podniz soglasnikov. Za soglasnike štejemo vse črke, ki niso samoglasniki (a, e, i, o, u). Tule je nekaj primerov besed, poleg vsake besede smo zapisali iskano dolžino:

  in 1
  pristno 3
  toreador 1
  strjenka 4
  a 0
  skrbstvo 7
  besedna 2
  krt 3

Naloga

Napiši funkcijo naj_soglasniki(datoteka), ki bo prebrala zaporedje besed z datoteke in vrnila niz z besedo, ki je vsebovala najdaljši strnjeni podniz soglasnikov. V zgornjem primeru bi torej izpisal besedo „skrbstvo“. Če je več besed z enako največjo dolžino podniza, je vseeno, katero od njih bo tvoj program izpisal.

Vhodni podatki

Datoteka z besedami, ki ima največ $100$ vrstic. Upoštevaj tudi morebitne presledke v vrsticah (presledek prekine zaporedje).

Izhodni podatki

Niz z besedo, ki ima najdaljše zaporedje soglasnikov.

Komentar

na tekmovanju je bilo zahtevano branje in pisanje s standardnim vhodom.

Uradna rešitev

def naj_soglasniki(datoteka):
    '''Poišče besedo, ki vsebuje najdaljše zaporedje soglasnikov
       in jo izpiše'''
    dat1 = open(datoteka, 'r', encoding='utf-8').readlines()
    dat = []
    for vrstica in dat1:
        dat.append(vrstica.strip('\n'))
    stevec_soglasnikov = 0
    naj = 0
    for beseda in dat:
        for crka in beseda:
            if crka not in 'aeiou ':
                stevec_soglasnikov += 1
            if crka in 'aeiou ':
                if naj < stevec_soglasnikov:
                    naj = stevec_soglasnikov
                    naj_beseda = beseda
                stevec_soglasnikov = 0
    return naj_beseda.strip(' ')